{--
    A number chain is created by continuously adding the square of the digits 
    in a number to form a new number until it has been seen before.
    
    For example,
    
    44  32  13  10  1  1
    85  89  145  42  20  4  16  37  58  89
    
    Therefore any chain that arrives at 1 or 89 will become stuck in an 
    endless loop. 
    What is most amazing is that EVERY starting number will eventually 
    arrive at 1 or 89.
    
    How many starting numbers below ten million will arrive at 89?
-}

module examples.Euler92 where

import frege.data.List
import frege.test.QuickCheck

-- You are the 13904th person to have solved this problem.
-- runtime 191.446 wallclock seconds. (first version with Map and canonic numbers)
-- runtime 32.967 wallclock seconds.  (with array and Int instead Long)
-- runtime 1.611 wallclock seconds (by using squaresum instead (sqsum • digits))
-- runtime 1.426 wallclock seconds. (with strict limit and array)
-- Level 3 Rank 357

-- limit = 10_000_000 

main _  = do 
        quickCheck prop_sq
        println result 
    where
        !limit = 10_000_000
        n600 = [1..600]  -- because max sqsum is 7*9²
        !array = arrayFromIndexList (zip n600 (map chain n600))
        result = loop 0 2
        loop !acc !n 
            | n < limit = loop (acc + array.[squaresum n]) (n+1)           
            | otherwise = acc 

{-- @chain n@ is 1 if the chain for
    n ends with 89 and 0 otherwise -}
chain !n 
    | n == 1  = 0
    | n == 89 = 1
    | otherwise = chain (squaresum n)


--- an optimised function to fuse sqsum and digits and avoid lists
squaresum n = loop 0 n
    where
        loop acc 0 = acc
        loop acc k = case k `rem` 10 of 
                        r -> loop (acc + r*r) (k `quot` 10)

--- the sum of the squares in the input list
sqsum xs = sqsum 0 xs where
    sqsum :: Int -> [Int] -> Int
    sqsum acc (i:is) = sqsum (acc+(i * i)) is
    sqsum acc []     = acc

--- gets the digits of a positive number and interprets them as integers
digits :: Int -> [Int]
digits = map ichr • unpacked • show
    where
        ichr :: Char -> Int
        ichr c = ord c - ord '0' 

--- gives a representation of the number so that smaller numbers come first
--- e.g. 1024 -> 124
canonic n = fold (\a \n -> a * 10L + Int.long n) 0L (sort (digits n))

--- make sure that 'squaresum' computes the same as (sqsum•digits)
--- (for positive integers, that is)
prop_sq = property (\k -> let n = abs k in sqsum (digits n) == squaresum n)        
        